﻿//有 n 个活动即将举办，每个活动都有开始时间与活动的结束时间，
//第 i 个活动的开始时间是 starti, 第 i 个活动的结束时间是 endi, 
//举办某个活动就需要为该活动准备一个活动主持人。
//
//一位活动主持人在同一时间只能参与一个活动。
//并且活动主持人需要全程参与活动，换句话说，
//一个主持人参与了第 i 个活动，那么该主持人在(starti, endi) 这个时间段不能参与其他任何活动。
//求为了成功举办这 n 个活动，最少需要多少名主持人。
//
//数据范围 :1≤n≤10^5，−2^32≤starti≤endi≤2^31−1
//
//复杂度要求：时间复杂度O(nlogn) ，空间复杂度O(n)

//输入：
//	2, [[1, 2], [2, 3]]
//返回值：
//	1
//说明：只需要一个主持人就能成功举办这两个活动
//
//输入：
//	2, [[1, 3], [2, 4]]
//返回值：
//	2
//说明：需要两个主持人才能成功举办这两个活动

class Solution {
public:
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        sort(startEnd.begin(), startEnd.end());
        priority_queue<int, vector<int>, greater<int>> heap; // 创建⼀个⼩根堆
        heap.push(startEnd[0][1]); // 先把第⼀个区间放进去
        for (int i = 1; i < n; i++) { // 处理剩下的区间
            int a = startEnd[i][0], b = startEnd[i][1];
            if (a >= heap.top()) { // 没有重叠
                heap.pop();
                heap.push(b);
            }
            else { // 有重叠
                heap.push(b); // 重新安排⼀个⼈
            }
        }
        return heap.size();
    }
};




